/*
 * @Author: 缄默
 * @Date: 2021-11-17 15:26:30
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-17 16:59:48
 */

//打气球的最大分数

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

int getMaxScore(vector<int>& arr);

int coins1(vector<int>& arr);
int process(vector<int>& arr, int L, int R);
int coins2(vector<int>& arr);

int main() {
    vector<int> arr({3, 2, 5});
    cout << getMaxScore(arr) << endl;
    cout << coins1(arr) << endl;
    cout << coins2(arr) << endl;
    return 0;
}

//仔细想了想 这算法居然是O（n的n次方。。。） 不可用
int getMaxScore(vector<int>& arr) {
    if (arr.size() == 0) return 0;
    //赋初始值 部分运算未进入循环 num 无初始值
    int max = 0;
    int leftL, rightR;
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == 0) continue;
        
        int cur = arr[i];

        int left = i - 1;
        while (left >= 0 && arr[left] == 0) {
            left--;
        }
        if (left < 0) {
            leftL = 1;
        }
        else {
            leftL = arr[left];
        }

        int right = i + 1;
        while (right < arr.size() && arr[right] == 0) {
            right++;
        }
        if (right < arr.size()) {
            rightR = arr[right];
        }
        else {
            rightR = 1;
        }

        int num = leftL * arr[i] * rightR;
        arr[i] = 0;
        num += getMaxScore(arr);
        max = max < num ? num : max;
        arr[i] = cur;
    }
    return max;
}

int coins1(vector<int>& arr) {
    if (arr.size() == 0) return 0;
    if (arr.size() == 1) return arr[0];
    vector<int> help;
    help.push_back(1);
    for (auto x : arr) {
        help.push_back(x);
    }
    help.push_back(1);
    return process(help, 1, arr.size());
}
//打爆arr上[L, R]范围的所有气球
int process(vector<int>& arr, int L, int R) {
    if (L == R) return arr[L] * arr[L - 1] * arr[R + 1];
    int maxNum = max(arr[L] * arr[L - 1] * arr[R + 1] + process(arr, L + 1, R), arr[R] * arr[R + 1] * arr[L - 1] + process(arr, L, R - 1));
    for (int i = L + 1; i < R; i++) {
        maxNum = max(maxNum, process(arr, L, i - 1) + arr[i] * arr[i - 1] * arr[i + 1] + process(arr, i + 1, R));
    }
    return maxNum;

}


int coins2(vector<int>& arr) {
    if (arr.size() == 0) return 0;
    if (arr.size() == 1) return arr[0];
    vector<int> help;
    help.push_back(1);
    for (auto x : arr) {
        help.push_back(x);
    }
    help.push_back(1);
    vector<vector<int>> dp(help.size(), vector<int>(help.size()));
    for (int i = 1; i <= arr.size(); i++) {
        dp[i][i] = help[i] * help[i - 1] * help[i + 1];
    }
    for (int L = arr.size(); L >= 1; L--) {
        for (int R = L + 1; R <= arr.size(); R++) {
            //求解dp[L][R] 表示打爆help[L][R]上的所有气球
            //最后打包L的方法
            int finalL = help[L - 1] * help[L] * help[R + 1] + dp[L + 1][R];
            int finalR = help[L - 1] * help[R] * help[R + 1] + dp[L][R - 1];
            dp[L][R] = max(finalL, finalR);
            for (int i = L + 1; i < R; i++) {
                dp[L][R] = max(dp[L][R], help[L - 1] * help[i] * help[R + 1] + dp[L][i - 1] + dp[i + 1][R]);
            }
        }
    }
    return dp[1][arr.size()];
}
